package cn.xaut.数组;

import java.util.*;

public class demo438 {

    // 优化方法
    // 滑动窗口
    // 时间复杂度：O(n)
    public List<Integer> findAnagrams2(String s, String p) {

        int[] freq = new int[256];

        int diff = p.length();
        char[] cs = s.toCharArray();
        int len = s.length();
        for (char c : p.toCharArray())
            freq[c]++;

        List<Integer> res = new ArrayList<>();
        int l = 0, r = 0;
        while (r < len) {
            if (freq[cs[r]] >= 1) { // 是 p 中的字符

                freq[cs[r]]--;
                diff--;
                r++;

                if (diff == 0)
                    res.add(l);
            } else {

                while (freq[cs[r]] <= 0 && l < r) {
                    diff++;
                    freq[cs[l]]++;
                    l++;
                }

                while (r < len && l == r && freq[cs[r]] < 1) {
                    l++;
                    r++;
                }
            }
        }
        
        return res;
    }

    // 笨方法
    // 时间复杂度：O( (n^2) * (log n) ) )
    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> res = new ArrayList<>();
        char[] ps = p.toCharArray();
        Arrays.sort(ps);

        for (int i = 0; i < s.length() - p.length() + 1; i++) {
            char[] ss = s.substring(i, i + p.length()).toCharArray();
            Arrays.sort(ss);
            boolean flag = true;
            for (int j = 0; j < ss.length; j++) {
                if (ss[j] != ps[j])
                    flag = false;
            }
            if (flag)
                res.add(i);
        }

        return res;
    }

    public static void main(String[] args) {

        System.out.println(new demo438().findAnagrams2("cbaebabacd", "abc"));//[0, 6]
    }
}
